<!DOCTYPE html>
<html lang=zh>
<head><meta name="generator" content="Hexo 3.9.0">
    <!-- so meta -->
    <meta charset="utf-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="HandheldFriendly" content="True">
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
    <meta name="description" content="前言今天是我使用leetcode学习算法的第一天，记录下自己的解题过程，以及学习到的东西 问题描述 Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exa">
<meta property="og:type" content="website">
<meta property="og:title" content="Two Sum question">
<meta property="og:url" content="https://andyliwr.github.io/others/leetcode/two_sum.html">
<meta property="og:site_name" content="月光倾城的代码小屋">
<meta property="og:description" content="前言今天是我使用leetcode学习算法的第一天，记录下自己的解题过程，以及学习到的东西 问题描述 Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exa">
<meta property="og:locale" content="zh-CN">
<meta property="og:updated_time" content="2020-01-15T06:30:09.120Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Two Sum question">
<meta name="twitter:description" content="前言今天是我使用leetcode学习算法的第一天，记录下自己的解题过程，以及学习到的东西 问题描述 Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exa">
    
    
        
          
              <link rel="shortcut icon" href="/images/favicon.ico">
          
        
        
          
            <link rel="icon" type="image/png" href="/images/favicon-192x192.png" sizes="192x192">
          
        
        
          
            <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon.png">
          
        
    
    <!-- title -->
    <title>Two Sum question</title>
    <!-- styles -->
    <link rel="stylesheet" href="/css/style.css">
    <!-- persian styles -->
    
      <link rel="stylesheet" href="/css/rtl.css">
    
    <!-- rss -->
    
    
</head>

<body class="max-width mx-auto px3 ltr">
    
    <div class="content index py4">
        
          <header id="header">
  <a href="/">
  
    
      <div id="logo" style="background-image: url(https://file.lantingshucheng.com/1544183173428.ico);"></div>
    
  
    <div id="title">
      <h1>月光倾城的代码小屋</h1>
    </div>
  </a>
  <div id="nav">
    <ul>
      <li class="icon">
        <a href="#"><i class="fas fa-bars fa-2x"></i></a>
      </li>
       
        <li><a href="/">首页</a></li>
       
        <li><a href="/archives/">归档</a></li>
       
        <li><a href="/search/">搜索</a></li>
       
        <li><a href="/tags/">标签</a></li>
       
        <li><a href="/others/">其他文章</a></li>
      
    </ul>
  </div>
</header>

        
        <article class="post" itemscope itemtype="http://schema.org/BlogPosting">
  

  <div class="content" itemprop="articleBody">
      
        <h3 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h3><p>今天是我使用leetcode学习算法的第一天，记录下自己的解题过程，以及学习到的东西</p>
<h3 id="问题描述"><a href="#问题描述" class="headerlink" title="问题描述"></a>问题描述</h3><blockquote>
<p>Given an array of integers, return indices of the two numbers such that they add up to a specific target.<br>You may assume that each input would have exactly one solution, and you may not use the same element twice.<br>Example:<br><figure class="highlight angelscript"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">Given nums = [<span class="number">2</span>, <span class="number">7</span>, <span class="number">11</span>, <span class="number">15</span>], target = <span class="number">9</span>,</span><br><span class="line">Because nums[<span class="number">0</span>] + nums[<span class="number">1</span>] = <span class="number">2</span> + <span class="number">7</span> = <span class="number">9</span>,</span><br><span class="line"><span class="keyword">return</span> [<span class="number">0</span>, <span class="number">1</span>].</span><br></pre></td></tr></table></figure></p>
</blockquote>
<p>我的四级英语翻译：</p>
<blockquote>
<p>给定一个整数数组，返回两个数字的索引，使它们相加到特定目标。<br>您可以假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。</p>
</blockquote>
<p>虽然是个算法菜鸟，我还是能写出解答的，第一次提交的算法是这样的：<br><figure class="highlight zephir"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> &#123;number[]&#125; nums</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@param</span> &#123;number&#125; target</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@return</span> &#123;number[]&#125;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">var</span> twoSum = <span class="function"><span class="keyword">function</span><span class="params">(nums, target)</span> </span>&#123;</span><br><span class="line">    <span class="keyword">let</span> result = []</span><br><span class="line">    outer: <span class="comment">// 外层循环标记</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">let</span> i=<span class="number">0</span>; i&lt;nums.length; i++) &#123;</span><br><span class="line">      <span class="keyword">let</span> max = nums.length - i <span class="number">-1</span>;</span><br><span class="line">      <span class="keyword">for</span>(<span class="keyword">let</span> j=<span class="number">1</span>; j&lt;=max; j++) &#123;</span><br><span class="line">        <span class="keyword">if</span> (nums[i] + nums[i+j] === target) &#123;</span><br><span class="line">          result = [i, i+j]</span><br><span class="line">          <span class="keyword">break</span> outer</span><br><span class="line">        &#125;</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<p>算法执行通过了，时间是163ms，竟然只打败了36%的人，也就是还有64%的人算法比我优秀 &gt;_&lt;</p>
<font color="#666666" size="2">PS: Javascript允许跳出指定循环，方法就是在循环迁定义一个 tag，然后将跳出循环的语句变成 break tag 就好了</font>

<p>然后我又改进了下自己的算法，变成了下面这个：<br><figure class="highlight perl"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line">var twoSum = function(nums, target) &#123;</span><br><span class="line">    let result = []</span><br><span class="line">    <span class="keyword">for</span>(let i=<span class="number">0</span>; i&lt;nums.length; i++) &#123;</span><br><span class="line">      let <span class="function"><span class="keyword">sub</span> = <span class="title">nums</span>.<span class="title">slice</span></span>(i+1);</span><br><span class="line">      let <span class="keyword">index</span> = <span class="function"><span class="keyword">sub</span>.<span class="title">indexOf</span>(<span class="title">target</span> - <span class="title">nums</span>[<span class="title">i</span>])</span></span><br><span class="line"><span class="function">      <span class="title">if</span> (<span class="title">index</span> &gt; -1) </span>&#123;</span><br><span class="line">        result = [i, i+<span class="keyword">index</span>+<span class="number">1</span>]</span><br><span class="line">      &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> result</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure></p>
<p>自以为信心满满，结果跑出来的结果比上一次还差，用了240ms，看来用js内置的方法并不能减少算法的执行时间<br>没办法了我已经黔驴技穷了，只能去别人的代码了。</p>
<figure class="highlight matlab"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">var twoSum = <span class="function"><span class="keyword">function</span><span class="params">(nums, target)</span> &#123;</span></span><br><span class="line">  let dict = &#123;&#125;</span><br><span class="line">  <span class="keyword">for</span>(var <span class="built_in">i</span> = <span class="number">0</span>; <span class="built_in">i</span>&lt;nums.<span class="built_in">length</span>; <span class="built_in">i</span>++) &#123;</span><br><span class="line">    let inp = nums[<span class="built_in">i</span>];</span><br><span class="line">    let diff = target-inp;</span><br><span class="line">    <span class="keyword">if</span>(diff in dict) <span class="keyword">return</span> [dict[diff], <span class="built_in">i</span>];</span><br><span class="line">    dict[inp] = <span class="built_in">i</span>;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> null;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>大神的代码大致思想就是，将数组转化成带索引的对象，然后每次循环的时候判断目标值减去当前值最后剩余的值在不在对象中，在的话就得到了结果。<br>这种方法是要聪明很多，将原来的O(n^2)的复杂度降低到了O(n)</p>
<h3 id="心得体会"><a href="#心得体会" class="headerlink" title="心得体会"></a>心得体会</h3><ol>
<li>javascript跳出指定循环的方法</li>
<li>用js内置的方法并不能减少算法的执行时间</li>
<li>比我厉害的人还很多很多呀，多努力</li>
</ol>

      
  </div>
</article>

        
        <footer id="footer">
  <div class="footer-left">
    Copyright &copy; 2020 Dikang Li
  </div>
  <div class="footer-right">
    <nav>
      <ul>
         
          <li><a href="/">首页</a></li>
         
          <li><a href="/archives/">归档</a></li>
         
          <li><a href="/search/">搜索</a></li>
         
          <li><a href="/tags/">标签</a></li>
         
          <li><a href="/others/">其他文章</a></li>
        
      </ul>
    </nav>
  </div>
</footer>

    </div>
</body>
</html>
<!-- styles -->
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
<link rel="stylesheet" href="/lib/justified-gallery/css/justifiedGallery.min.css">
<link rel="stylesheet" href="/lib/fancybox/jquery.fancybox.css">

<link rel="stylesheet" href="https://file.lantingshucheng.com/blog/v3/static/styles/gitalk.css">


<!-- jquery -->
<script src="/lib/jquery/jquery.min.js"></script>
<script src="/lib/justified-gallery/js/jquery.justifiedGallery.min.js"></script>
<script src="/lib/fancybox/jquery.fancybox.pack.js"></script>

<script type="text/javascript" src="https://file.lantingshucheng.com/blog/v3/static/scripts/md5.js"></script>
<script type="text/javascript" src="https://file.lantingshucheng.com/blog/v3/static/scripts/gitalk.min.js"></script>

<script src="/js/main.js"></script>
<!-- search -->

<!-- Google Analytics -->

<!-- Baidu Analytics -->

    <script type="text/javascript">
        var _hmt = _hmt || [];
        (function() {
            var hm = document.createElement("script");
            hm.src = "https://hm.baidu.com/hm.js?7851ca7a86be957be994acb77639a5be";
            var s = document.getElementsByTagName("script")[0];
            s.parentNode.insertBefore(hm, s);
        })();
    </script>

<!-- Disqus Comments -->


  <script type="text/javascript">
    window.onload = function(){
      if (window.location.href.indexOf('andyliwr.github.io') > -1) {
        var gitalk = new Gitalk({
          clientID: 'ad6f70df0c70d2b715f9',
          clientSecret: '40384bee244c1e17dd7c37733d21e9ef669e969c',
          repo: 'Andyliwr.github.io',
          owner: 'Andyliwr',
          admin: ['Andyliwr'],
          id: md5(location.pathname),
          distractionFreeMode: 'true'
        })
        gitalk.render('gitalk_thread')
      }
    }
  </script>


